package com.ag.improvedjava.collections.sort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import com.ag.improvedjava.utils.Requires;

class QuickSort implements Sort {

	@Override
	public <T extends Comparable<? super T>> Collection<T> sort(
			Collection<T> collection) {
		Requires.requireNonNull(collection,
				"The input collection can not be null.");
		
		Object[] array = collection.toArray();
		quickSort(array, 0, array.length - 1);
		
		List<T> result = new ArrayList<>(array.length);
		for (Object o : array) {
			@SuppressWarnings("unchecked")
			T t = (T) o;
			result.add(t);
		}
		return result;
	}

	private void quickSort(Object[] array, int left, int right) {
		
		if (left < right) {
			int pivotIndex = left + (right - left) / 2;
			pivotIndex = partition(array, left, right, pivotIndex);
			quickSort(array, left, pivotIndex - 1);
			quickSort(array, pivotIndex + 1, right);
		}
		
	}

	// left is the index of the leftmost element of the subarray
	// right is the index of the rightmost element of the subarray (inclusive)
	// number of elements in subarray = right-left+1
	private int partition(Object[] array, int left, int right, int pivotIndex) {
		
		@SuppressWarnings("unchecked") // Safe cast as the array was 
		// built from a Collection of Comparable<? super T>
		Comparable<Object> pivotValue = (Comparable<Object>) array[pivotIndex];
		swapArrayElements(array, pivotIndex, right); // we move the pivot to the end
		int storeIndex = left;
		
		for (int i = left ; i < right ; i++) {
			if (pivotValue.compareTo(array[i]) > 0) {
				swapArrayElements(array, i, storeIndex++);
			}
		}
		
		swapArrayElements(array, right, storeIndex); // we move the pivot to its final place
		return storeIndex;
	}
	
	private void swapArrayElements(Object[] array, int x, int y) {
		if (x == y) return;
		Object elemAtX = array[x];
		array[x] = array[y];
		array[y] = elemAtX;
	}
}
